//If array index start at '1', will make this code easier.
namespace llt
{
	
	namespace heap
	{
		//rebuilt a heap by 
		template<typename T>
		inline void heapRebuilt( T* data, int size, int pos=1 )
		{
#define L_Index (2*pos-1)
#define R_Index (2*pos)
#define C_Index (pos-1)
			
#define L_Data *(data+L_Index)
#define R_Data *(data+R_Index)
#define C_Data *(data+C_Index)
			
#define swap(x,y) \
		{\
			T temp = (x);\
			(x) = (y);\
			(y) = temp;\
		}
			
			for ( ; ; )
			{
				if ( 2*pos > size )
				{
					break;
				}
				else if ( 2*pos == size )                         //only l-child
				{
					if ( C_Data < L_Data )
					{
						swap(C_Data, L_Data)
					}
					break;
				}
				else if ( L_Data <= C_Data && R_Data <= C_Data )  //right < left < current
				{
					break;
				}
				else if ( L_Data >= C_Data && R_Data >= C_Data )   //both child r bigger than current
				{
					if ( L_Data > R_Data )                         //left > right > current
					{
						swap(C_Data, L_Data);
						pos = 2*pos;
					}
					else                                           //right > left > current
					{
						swap(C_Data, R_Data);
						pos = 2*pos+1;
					}
				}
				else if ( L_Data >= C_Data && R_Data <= C_Data )    //left > current > right
				{
					swap(C_Data, L_Data);
					pos = 2*pos;
				}
				else if ( R_Data >= C_Data  && L_Data <= C_Data  )  //right > current > left
				{
					swap(C_Data, R_Data);
					pos = 2*pos+1;
				}
			}//end of for(;;)
			
#undef L_Index
#undef R_Index
#undef C_Index
			
#undef L_Data
#undef R_Data
#undef C_Data
#undef swap
		}//end of heapRebuilt()
		
		template<typename T>
		inline void heapSort(T* data, int size)
		{
			int i;
			T temp;
			for ( i=size/2; i>0; i-- )
			{
				heapRebuilt<T>(data, size, i);
			}
			
			for ( i=size; i>1; i-- )
			{
				temp = *data;
				*data = *(data+i-1);
				*(data+i-1) = temp;
				heapRebuilt<T>(data, i-1, 1);
			}
			
		}
	}//end of namespace heap




	namespace BTree
	{

	}
	
}//end of namespace llt